#include <stdio.h>
#include "head.h"
#include <stdlib.h>
#include <err.h>


/**
* 对copy指令重新排序，并破坏依赖关系
*/
int reOrder(Block *blocks,int blockCount,int *order){

    Graph graph;
    graph.VertexNum = blockCount;
	Vertex *v = malloc((blockCount+1)*sizeof(Vertex));

	int **cost;
	cost =(int**)malloc(sizeof(int*)*blockCount);  
    for(int i=0; i<blockCount; i++)  
        cost[i]=(int*)malloc(sizeof(int)*blockCount);  
    for(int i=0;i<graph.VertexNum;i++){
        Vertex ver;
        ver.number=i;ver.p=NULL;
        v[i]=ver;
    }
    graph.vertex = v;

	GNode *nodes = malloc((blockCount+1)*sizeof(GNode));
    for(int i=0;i<blockCount;i++){
        nodes[i].number=i;
        nodes[i].next=NULL;
    }

    for(int f=0;f<blockCount;f++){
        for(int t=0;t<blockCount;t++){
			cost[f][t] = ifConflict(blocks,f,t);
			if(cost[f][t]>0)
			{
                GNode *gNode;
                gNode=malloc(sizeof(GNode));
                gNode->number=t;
                gNode->next=nodes[f].next;
                nodes[f].next=gNode;   
            }
        }
    }


    graph.LinkTable = nodes;
    int orderCount = searchByDepthFirst(&graph,order,blocks,cost);
	if(blockCount != orderCount) errx(1, "reorder error\n");
   	return orderCount;
}


/**
* 深度优先搜索，要求输入图g的结点编号从0开始
*/
int searchByDepthFirst(Graph *g,int *order,Block *blocks,int **cost)
{
	int VertexNum = g->VertexNum;
	Stack *stack = initStack();
	Vertex *vs = g->vertex;
	GNode *linkTable = g->LinkTable;
	int index = 0;
	int costsum = 0;
	Stack *lastStackGray = NULL;

	for (int i = 0; i < VertexNum; i++)
	{
		Vertex *v = vs + i;
		v->color = Vertex_WHITE;
		v->p = NULL;
	}
	
	while (index<VertexNum) 
	{	

		if(isEmpty(stack)){
			for(int i=0;i<VertexNum;i++){
				if(vs[i].color==Vertex_WHITE){
					push(&stack, i);
					stack->preGray = lastStackGray;
					break;
				}
			}
		}
		if(stack==lastStackGray){
			lastStackGray = stack->preGray;
		}
		int number = pop(&stack);
		Vertex *u = vs + number;
		if (u->color == Vertex_WHITE) 
		{
			// 开始搜索该结点的子结点
			u->color = Vertex_GRAY;
			push(&stack, number);
			stack->preGray=lastStackGray;
			lastStackGray = stack;
		}
		else if (u->color == Vertex_GRAY)
		{
			// 该结点的子结点已经被搜索完了
			u->color = Vertex_BLACK;
			order[index]=u->number;
			u->f = index++;
			if(ifdebug) printf("finish%d:%d,all:%d\n",index,u->number,VertexNum);
			continue;
		}
		else
		{	
			continue;
		}
		GNode *links = linkTable + number;
		links = links->next;
		while (links != NULL)
		{
			// 展开子结点并入栈
			Vertex *v = vs + links->number;
			if(cost[number][links->number]==0){
				links = links->next;
				continue;
			}
			if (v->color == Vertex_WHITE)
			{
				v->p = u;
				push(&stack, links->number);
				stack->preGray = lastStackGray;
			}
			if(v->color == Vertex_GRAY){
				if(ifdebug) printf("\n\n\n\nconflict:%d\n",v->number);
				
				push(&stack, links->number);
				stack->preGray = lastStackGray;
				int blockf = 0;
				int blockt = 0;
				findMinNodeInCycle(stack,cost,vs,v->number,&blockf,&blockt);

				while(!isEmpty(stack)){
					int top = pop(&stack);
					if(vs[top].color==Vertex_GRAY){
						vs[top].color=Vertex_WHITE;
					}
				}
				lastStackGray = NULL;

				costsum += transform(blocks,blockf,blockt);
				cost[blockf][blockt]=0;
				break;
			}
			links = links->next;
		}
	}
	if(ifdebug) printf("costSum:%d\n",costsum);
	return index;
}

void findMinNodeInCycle(Stack *s,int **cost,Vertex *v,int vn,int *blockf,int *blockt){
	*blockf = vn;
	*blockt = vn;
	int min = __INT_MAX__;
	int pre = s->value;
	s = s->preGray;
	int curr;
	while (!isEmpty(s))
	{	

		curr = s->value;
		if(cost[curr][pre]<min&&cost[curr][pre]>0){
			min = cost[curr][pre];
			*blockf = curr;
			*blockt = pre;
		}
		pre = curr;
		s = s->preGray;
		if(curr==vn) break;
	}
	if(ifdebug) printf("findMinNodeInCycle:%d,%d\n",*blockf,*blockt);
}

//是否存在Copy from fblock to tblock
int ifConflict(Block *blocks,int fb,int tb){
	if(fb==tb) return 0;
	Block fblock = blocks[fb];
	Block tblock = blocks[tb];
	int start = fblock.startPos;
	int end = fblock.endPos;
	int cost = 0;
	for(int i=0;i<tblock.cmdCount;i++){
		if(tblock.cmds[i].type==0) continue;
		off_t f = tblock.cmds[i].f;
		off_t l = tblock.cmds[i].l;
		if(f>=start&&f<=end || f+l-1>=start&&f+l-1<=end){
			cost += l;
		}
	}
	return cost;
}

//解决块之间的冲突
int transform(Block *blocks,int blockf,int blockt){
	if(blockf==blockt){
		errx(1, "transform error\n");
	}
	off_t start = blocks[blockf].startPos;
	off_t end = blocks[blockf].endPos;
	off_t sum = 0;
	for(int i=0;i<blocks[blockt].cmdCount;i++){
		if(blocks[blockt].cmds[i].type==0) continue;
		off_t f = blocks[blockt].cmds[i].f;
		off_t l = blocks[blockt].cmds[i].l;
		if(f>=start&&f<=end || f+l-1>=start&&f+l-1<=end){
			blocks[blockt].cmds[i].type = 0;
			sum += blocks[blockt].cmds[i].l;
		}
	}
	return sum;

}

